/**
 * \file nfa.h
 * \brief An implementation of NFA for Unicode character matching. This file
 * contains the functions that are common to implementations of Rscript's
 * regular expression matching, assembler and the language.
 **/

#ifndef R_NFA_H
#define R_NFA_H

#include "standard.h"
#include "vector.h"
#include "utf8.h"

/****************************************************************************
 * NFA node
 ***************************************************************************/

/* Types of matching classes: */
enum NFAMatchClassTypeT {
  R_NFA_CLASS_ANY, /* This node accepts any character (dot or '.') */
  R_NFA_CLASS_SINGLE, /* This node accepts a single character, given in
                        * extra_1 */
  R_NFA_CLASS_RANGE, /* This node accepts a range of characters, such that
                       * extra_1 <= char <= extra_2 */
};
typedef enum NFAMatchClassTypeT NFAMatchClassType;

/**
 * \brief A matching class for a CHAR NFA.
 **/
struct NFAMatchingClassT {
  NFAMatchClassType type;
  uni_char extra1;
  uni_char extra2;
};
typedef struct NFAMatchingClassT NFAMatchingClass;

/* Types of nodes in a NFA: */
enum NFANodeTypeT {
  R_NFA_NODE_CHAR, /* This node tests the current unicode character. */
  R_NFA_NODE_NOT_CHAR, /* This node tests if it doesn't belong to the given
                         * character classes (used when [^...] in expression).
                         */
  R_NFA_NODE_SPLIT, /* This node simply splits into other NFAs. */
  R_NFA_NODE_TERM, /* This node acts like a matching state. */
};
typedef enum NFANodeTypeT NFANodeType;

/**
 * \brief A general node in an NFA. A network of NFA nodes (defined by a
 * pointer to the starting node) is the static portion of the NFA. The node
 * structures do not change inside while mathing is taking place. The dynamic
 * portion of the matching is contained in the NFAState structure.
 **/
struct NFANodeT {
  NFANodeType type;
  union {
    /* If node is a CHAR */
    struct {
      RVector match_classes;
      struct NFANodeT* next; /* If the match classes are satisfied, this is
                              * the node propagated to. */
    } nfa_char;

    /* If node is a SPLIT */
    struct {
      RVector splits;
    } nfa_split;

    /* If node is a TERM */
    struct {
      int id;
    } nfa_term;
  };
  struct NFANodeT* extra; /* An extra pointer to some node, used as a linked
                           * list of output nodes when generating regexp. */
};
typedef struct NFANodeT NFANode;

/**
 * \brief Add a child to a Split NFA node.
 **/
void r_nfanode_add_child(NFANode* node, NFANode* target);

/**
 * \brief Add a class to a Char NFA node.
 **/
void r_nfanode_add_class(NFANode* node, NFAMatchClassType type,
                          uni_char extra_1, uni_char extra_2);

/**
 * \brief Initialize a new Char node. Use #num_classes to define the number of
 * classes you expect to have (this memory will then be preallocated). It will
 * still be possible to dynamically add more classes.
 **/
void r_nfanode_init_char(NFANode* node, int num_classes);

/**
 * \brief Initialize a new Split node. Use #num_splits to define number of splits
 * you expect to have (memory will be preallocated).
 **/
void r_nfanode_init_split(NFANode* node, int num_splits);

/**
 * \brief Initialize a new Term node.
 **/
void r_nfanode_init_term(NFANode* node, int id);

/**
 * \brief Set the next-node of a Char node.
 **/
#define r_nfanode_set_next(node, next_node) ((node)->nfa_char.next = (next_node))

/****************************************************************************
 * NFA state
 ***************************************************************************/
struct NFAStateT {
  RVector active_states;
};
typedef struct NFAStateT NFAState;

/**
 * \brief In a the given state #state, activate #node (add it to the list of
 * active nodes, or propagate through the Split nodes).
 **/
void r_nfastate_activate(NFAState* state, NFANode* node);

/**
 * \brief Returns the pointer to the i-th active node.
 **/
#define r_nfastate_active(state,i)  (*((NFANode**) r_vector_get( \
                                        &((state)->active_states), i)))

/**
 * \brief Any active states?
 **/
#define r_nfastate_any(state)  ((state)->active_states.size > 0)

/**
 * \brief Create a new NFAState.
 **/
void r_nfastate_init(NFAState* state);

/**
 * \brief Number of active states in the NFAState.
 **/
#define r_nfastate_num(state)  ((state)->active_states.size)

/**
 * \brief "Steps" through the NFA, "parsing" a single uni_char in the input.
 **/
void r_nfastate_step(NFAState* state, uni_char event);

#endif /* R_NFA_H */
